package sort.on;

/**
 * 计数排序（应用：高考分数段人数，年龄段人数）
 * 只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，
 * 就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，
 * 要将其在不改变相对大小的情况下，转化为非负整数
 *
 * @author yeyangtao created at 14:07 2020/9/28
 */
public class CountingSort {
    public static void countingSort(int[] a) {
        int size = a.length;
        if (size <= 1) return;
        //查找数组中的数据范围
        int max = a[0];
        for (int i = 1; i < size; i++) {
            if (max < a[i]) max = a[i];
        }
        // 申请一个计数数组c，下标大小[0,max]
        int[] c = new int[max + 1];
        for (int i = 0; i <= max; i++) {
            c[i] = 0;
        }
        //计算每个元素的个数放入c中
        for (int value : a) {
            c[value]++;
        }
        //依次累加
        for (int i = 1; i < max + 1; i++) {
            c[i] = c[i - 1] + c[i];
        }
        //临时数组r，存储排序之后的结果
        int[] r = new int[size];
        // 计算排序的关键步骤了，有点难理解
        for (int i = size - 1; i >= 0; i--) {
            int index = c[a[i]] - 1;
            r[index] = a[i];
            c[a[i]]--;
        }
        //将结果拷贝回a数组
        System.arraycopy(r, 0, a, 0, size);
    }
}
